home *** CD-ROM | disk | FTP | other *** search
/ Aminet 12 / Aminet 12 (1996)(GTI - Schatztruhe)[!][Jun 1996].iso / Aminet / dev / e / eiffel.lha / flc / framework / DICTIONARY < prev    next >
Encoding:
Text File  |  1996-01-21  |  1.8 KB  |  72 lines
  1.  
  2. -- DICTIONARY is an efficient data structure for named objects.
  3. -- Time complexity for data adding is O(log n).
  4. -- Time complexity for data searching is also O(log n).
  5. -- Space complexity is O(n).
  6.  
  7. indexing
  8.  
  9.   names: dictionary;
  10.   size: unlimited;
  11.   contents: named;
  12.  
  13.   author: "Guichard Damien";
  14.   created: 19,January,1996;
  15.   modified: 20,January,1996
  16.  
  17. class DICTIONARY inherit SORTED_TREE
  18.   rename nodes as articles
  19.   export {NONE} leaves
  20.   end
  21. creation make
  22. feature{ANY}
  23.   name:STRING
  24.   make(s:STRING) is
  25.     -- Create a dictionary element.
  26.     do
  27.       name := s
  28.     end  -- make
  29.   find (key:STRING):DICTIONARY is
  30.     -- Find first occurrence in the tree matching 'key'.
  31.     -- You should use 'continu' to find next occurrences.
  32.     local key_value:INTEGER
  33.     do
  34.       key_value := key.hash_code
  35.       from Result := Current
  36.       until
  37.         Result = Void or else Result.name.is_equal(key)
  38.       loop
  39.         if key_value < Result.name.hash_code then
  40.           Result := Result.left
  41.         else
  42.           Result := Result.right
  43.         end
  44.       end
  45.     end  -- find
  46.   continu:DICTIONARY is
  47.     -- Find next element in the tree that has same name.
  48.     -- Usually this is used on element returned by find.
  49.     do
  50.       if right /= Void then Result := right.find(name) end
  51.     end  -- continu
  52. feature{DICTIONARY}
  53.   is_less (other:like Current):BOOLEAN
  54.     -- Is 'other' less than current object?
  55.     do
  56.       Result := other.name.hash_code < name.hash_code
  57.     end;  -- is_less
  58. feature{ANY}
  59.   is_equal (other:like Current):BOOLEAN
  60.     -- Is 'other' equal to current object?
  61.     do
  62.       Result := name.is_equal(other.name)
  63.     end   -- greater
  64. feature{DICTIONARY}
  65.   is_greater (other:like Current):BOOLEAN
  66.     -- Is 'other' greater than current object?
  67.     do
  68.       Result := other.name.hash_code > name.hash_code
  69.     end   -- greater
  70. end  -- class 'DICTIONARY'
  71.  
  72.